class Solution {
public:
    /**
     * @param word1: A string
     * @param word2: A string
     * @return: The minimum number of steps.
     */
    int minDistance(string &word1, string &word2) 
    {
        // write your code here
        int l1 = word1.length();
        int l2 = word2.length();
        vector<vector<int>> dis (l1 + 1, vector<int>(l2 + 1));
        dis[0][0] = 0;
        for (int i = 1; i <= l1; i++)
        {
            dis[i][0] = i;
        }
        for (int i = 1; i <= l2; i++)
        {
            dis[0][i] = i;
        }
        for (int i = 1; i <= l1; i++)
        {
            for (int j = 1; j <= l2; j++)
            {
                // dis[i][j] = min(dis[i - 1][j - 1] + (word1[i - 1] == word2[j - 1]) ? 0 : 1, dis[i - 1][j]+ 1);
                dis[i][j] = min(dis[i - 1][j - 1] + ((word1[i - 1] == word2[j - 1]) ? 0 : 1), dis[i - 1][j]+ 1);
                dis[i][j] = min(dis[i][j], dis[i][j - 1] + 1);
            }
        }
        return dis[l1][l2];
    }
};